package com.hedl.practice.StudyAlgorithm.Insert_sort_directly;

import java.util.Arrays;

public class InsertSort {
    /**
     *      首先判断数组是否为空或长度为0，如果是则直接返回。
     *      从数组的第二个元素开始，遍历整个数组。
     *      对于数组的第i个元素，从i开始向前遍历，直到找到第一个比它小的元素的位置j。
     *      将i位置上的元素插入到j+1的位置上，同时将j+1到i-1的元素后移一位。
     *      重复步骤2到4，直到遍历完整个数组。
     * @param arr
     */
    public static void insertSort(Integer[] arr){
        if (arr == null || arr.length == 0) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            int target = arr[i];
            while (j > 0 && target < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = target;
        }
    }
    public static void main(String[] args) {
        Integer[] s = new Integer[]{46,18,12,38,20,43,24,65,23,23,85};
        insertSort(s);
        System.out.println(Arrays.toString(s));
    }
}
